package mo.leetcode_hot;

import java.util.*;

public class L17 {

    public List<String> letterCombinations(String digits) {
        if (digits.length() == 0) {
            return new ArrayList<>();
        }
        Map<Character, List<String>> digit2letter = new HashMap<>();
        digit2letter.put('2', Arrays.asList("a", "b", "c"));
        digit2letter.put('3', Arrays.asList("d", "e", "f"));
        digit2letter.put('4', Arrays.asList("g", "h", "i"));
        digit2letter.put('5', Arrays.asList("j", "k", "l"));
        digit2letter.put('6', Arrays.asList("m", "n", "o"));
        digit2letter.put('7', Arrays.asList("p", "q", "r", "s"));
        digit2letter.put('8', Arrays.asList("t", "u", "v"));
        digit2letter.put('9', Arrays.asList("w", "x", "y", "z"));
        LinkedList<String> res = new LinkedList<>();
        res.addAll(digit2letter.get(digits.charAt(0)));
        for (int i = 1; i < digits.length(); i++) {
            List<String> letters = digit2letter.get(digits.charAt(i));
            int size = res.size();
            while (size > 0) {
                String last = res.pollFirst();
                for (int j = 0; j < letters.size(); j++) {
                    StringBuilder builder = new StringBuilder(last);
                    builder.append(letters.get(j));
                    res.add(builder.toString());
                }
                size--;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        L17 test = new L17();
        System.out.println(test.letterCombinations("23"));
    }
}
